package com.mzy.linear_struct.subject;

/**
 * @Author: codermzy
 * @Date: 2024/04/27/下午12:34
 * @Description:
 */
public class 颜色分类75 {

    static class Solution {
        public void sortColors(int[] nums) {
            partition(nums, 0, nums.length - 1);
        }

        private void partition(int[] nums, int left, int right) {
            if (left >= right) {
                return;
            }
            int pivot = nums[right];

            int i = left, j = right - 1;

            while (i <= j) {
                while (nums[i] < pivot) {
                    i++;
                }

                while (j >= 0 && nums[j] > pivot) {
                    j--;
                }

                if (i <= j) {
                    swap(nums, i, j);
                    i++;
                    j--;
                }
            }

            swap(nums, i, right);
            partition(nums, left, j);
            partition(nums, i + 1, right);

        }

        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

    public static void main(String[] args) {

    }
}
